public class Solution4 {
    //给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点
    //方法一
    public ListNode middleNode(ListNode head) {
        if(head == null) {
            return null;
        }
        int len = size(head);
        int count = len / 2;
        ListNode cur = head;
        while(count != 0) {
            cur = cur.next;
            count--;
        }
        return cur;
    }
    public int size(ListNode head) {
        if(head == null) {
            return -1;
        }
        int count = 0;
        ListNode cur = head;
        while(cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }



      //方法二

    public ListNode middleNode2(ListNode head) {
        if(head == null) {
            return null;
        }
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) { //注意是&&，而不是||;并且要注意fast != null必须在前
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

}
